#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//typedef int STDatatype;
//typedef struct Stack
//{
//    STDatatype* a;
//    int top;
//    int capacity;
//}ST;
//bool StackEmpty(ST* ps)//空
//{
//    assert(ps);
//
//    return ps->top == 0;
//}
//void StackInit(ST* ps)//出
//{
//    assert(ps);
//    ps->a = NULL;
//    ps->top = 0; // -1
//    ps->capacity = 0;
//}
//
//void StackDestroy(ST* ps)//销毁
//{
//    assert(ps);
//    if (ps->a)
//    {
//        free(ps->a);
//    }
//    ps->a = NULL;
//    ps->top = 0;
//    ps->capacity = 0;
//}
//
//void StackPush(ST* ps, STDatatype x)//压
//{
//    assert(ps);
//
//    // 检查空间够不够，不够就增容
//    if (ps->top == ps->capacity)
//    {
//        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//        STDatatype* tmp = realloc(ps->a, sizeof(STDatatype)*newcapacity);
//        if (tmp == NULL)
//        {
//            printf("rellaoc fail\n");
//            exit(-1);
//        }
//        ps->a = tmp;
//        ps->capacity = newcapacity;
//    }
//
//    ps->a[ps->top] = x;
//    ps->top++;
//}
//
//void StackPop(ST* ps)//出
//{
//    assert(ps);
//    assert(!StackEmpty(ps));
//
//    --ps->top;
//}
//
//
//
//int StackSize(ST* ps)
//{
//    assert(ps);
//
//    return ps->top;
//}
//
//STDatatype StackTop(ST* ps)//取
//{
//    assert(ps);
//    assert(!StackEmpty(ps));
//
//    return ps->a[ps->top - 1];
//}
//
//bool isValid(char * s)
//{
//    ST st;
//    StackInit(&st);
//    int mach=false;
//    while(*s)
//    {
//        if((*s=='[')||(*s=='{')||(*s=='('))
//        {
//            StackPush(&st,*s);
//            s++;
//        }
//        else
//        {
//            if(StackEmpty(&st))
//            {
//                mach=true;
//                break;
//            }
//            char top=StackTop(&st);
//            StackPop(&st);
//            if((*s==']'&&top!='[')||
//               (*s=='}'&&top!='{')||
//               (*s==')'&&top!='('))
//                //if(*s!=top)
//            {
//                mach=true;
//                break;
//            }
//            else
//            {
//                s++;
//            }
//        }
//    }
//    if(mach==true)
//    {
//        mach=StackEmpty(&st);
//    }
//    StackDestroy(&st);
//
//    return mach;
//}
//
//int main()
//{
//    char arr[]="()";
//    isValid(arr);
//    return 0;
//}

//int compar(const void *p1,const void*p2)
//{
//    return (*(int*)p1)-(*(int*)p2);
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//    int a=m;
//    for(int i =0;i<n;i++)
//    {
//        nums1[a]=nums2[i];
//        a++;
//    }
//    qsort(nums1,n+m,sizeof(int),compar);
//}
//int i;
//void instead(int*nums1,int*arr,int m)
//{
//    for(i =0;i<m;i++)
//    {
//        arr[i]=*nums1;
//        nums1++;
//    }
//}
//
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//   int arr[m];
//    instead(nums1,arr,m);
//    int *a=arr;
//    int counta=m;
//    int countb=n;
//    for(i=0;i<m+n;i++)
//    {
//        if(*a<=*nums2&&counta>0)
//        {
//            *nums1=*a;
//            nums1++;
//            a++;
//            counta--;
//        }
//        else if(*a>*nums2&&countb>0)
//        {
//            *nums1=*nums2;
//            nums2++;
//            nums1++;
//        }
//    }
//
//}
//



struct ListNode {
    int val;
   struct ListNode *next;
 };



//struct ListNode* removeElements(struct ListNode* head, int val)//返回指针接口
//{
//    if(head==NULL)
//    {
//        return NULL;
//    }
//    struct ListNode*  cur=head;
//    struct ListNode*  hind=head;
//    while(cur)
//    {
//        if(cur->val==val&&cur->next!=NULL)
//        {
//            struct ListNode*next=cur->next;
//            free(cur);
//            hind->next=next;
//            cur=next;
//        }
//        else if(cur->val==val&&cur->next==NULL)
//        {
//            free(cur);
//            hind->next=NULL;
//            cur=NULL;
//        }
//        if(hind->next!=NULL)
//        {
//            hind=cur;
//            cur=cur->next;
//        }
//
//    }
//    return head;
//}
//struct ListNode* reverseList(struct ListNode* head)
//{
//    struct ListNode* newlist=NULL;
//    struct ListNode*cur=head;
//    while(cur)
//    {
//        struct ListNode*next=cur->next;
//        struct ListNode*newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
//        newnode->next=next;
//        newnode->val=cur->val;
//        cur->next=newnode;
//        cur=cur->next->next;
//    }
//    cur=head;
//    while(cur)
//    {
//        struct ListNode* curnext=cur->next;
//        cur=curnext->next;
//        curnext->next=NULL;
//        if(newlist==NULL)
//        {
//            newlist=curnext;
//        }
//        else
//        {
//            struct ListNode*oldhead =newlist;
//            newlist=curnext;
//            newlist->next=oldhead;
//        }
//
//
//    }
//    return newlist;
//}

//struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
//{
//    if(l1==NULL&&l2==NULL)
//    {
//        return NULL;
//    }
//    struct ListNode*newlist=(struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode*cur=newlist;
//    while(l1&&l2)
//    {
//        if(l1->val<l2->val)
//        {
//            cur->next=l1;
//            l1=l1->next;
//
//        }
//        else
//        {
//            cur->next=l2;
//            l2=l2->next;
//        }
//
//        cur=cur->next;
//    }
//    if(l1==NULL)
//     cur->next=l2;
//    if(l2==NULL)
//     cur->next=l1;
//
//    struct ListNode*head=newlist->next;
//    free(newlist);
//    return head;
//}

//struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
//{
//    if(l1==NULL&&l2==NULL)
//    {
//        return NULL;
//    }
//    if(l1==NULL)
//    {
//        return l2;
//    }
//    if(l2==NULL)
//    {
//        l1;
//    }
//
//    struct ListNode*newlist=NULL;
//    struct ListNode*coaper=NULL;
//    if(l1->val<l2->val)
//    {
//        newlist=l1;
//        coaper=l2;
//    }
//    else
//    {
//        newlist=l1;
//        coaper=l2;
//    }
//    struct ListNode*cur=newlist->next;
//    while(coaper&&cur)
//    {
//        if(cur->val<coaper->val)
//        {
//            cur=cur->next;
//        }
//        else
//        {
//            struct ListNode*next=cur->next;
//            cur->next=coaper;
//            coaper=coaper->next;
//            cur=cur->next;
//            cur->next=next;
//        }
//
//    }
//    if(l1==NULL)
//      cur->next=l2;
//    if(l2==NULL)
//    cur->next=l1;
//    return newlist;
//}
int size(struct ListNode *head)
{
    int count=0;
    while(head)
    {
        ++count;
        head=head->next;
    }
    return count;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    int countA=size(headA);
    int countB=size(headB);

    //你不知道那个大其实也可以比较count,这里就是少写了一个else
    struct ListNode*fast=headA;
    struct ListNode*slow=headB;
    if(countA<countB)
    {
       fast=headB;
        slow=headA;
    }

    int foot=abs(countA-countB);
    while(foot--)
    {
        fast=fast->next;
    }
    while(fast&&slow)
    {
        if(fast==slow)
        {
            return fast;
        }
        fast=fast->next;
        slow=slow->next;
    }

    return NULL;
}
int main()
{
    struct ListNode*list=NULL;
    struct ListNode*list2=NULL;
    struct ListNode*n1= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n2= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n3= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n4= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n5= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n6= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n7= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n8= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n9= (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n10= (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val=4;
    n2->val=1;
    n1->next=n2;
    n2->next=n7;

    n4->val=5;
    n5->val=0;
    n6->val=1;
    n4->next=n5;
    n5->next=n6;
    n6->next=n7;


    n7->val=8;
    n8->val=4;
    n9->val=5;
    n7->next=n8;
    n8->next=n9;
    n9->next=NULL;



    list=n1;
    list2=n4;


//    struct ListNode*ret= removeElements(list,7);

    struct ListNode*ret=getIntersectionNode(list,list2);

    return 0;
}



